a. The Field of the Invention
This invention relates to the field of computer based modeling systems. In particular, the invention relates to the solution of constrained models.
b. Background Information
Computers can be used by people to model physical objects by using modeling applications. Allowing users to define models in terms of model objects and constraints is desirable. If a model object is constrained so that its location and dimensions are defined in relation to other model objects, it is easier for a user to model physical objects. Constraint satisfaction is the process of finding locations, dimensions, colors, speed, temperatures, etc., for model objects in accordance with the constraints specified in the model.
Models which are defined in terms of model objects and constraints are more easily modified by the user permitting greater design flexibility. The shortcoming of various approaches to providing constraint satisfaction has been the difficulty in handling different types of problems as well as difficulty handling large numbers of interdependent model objects. Previous approaches have provided a single monolithic constraint solver program. The monolithic solver program provided by previous approaches would be restricted to certain types of problems. Many physical objects have varied types of constraints. In the design of bridges for example, allowing the user to describe both structural and geometric constraints would simplify the modeling process. However, the ability to solve kinematic constraints would be more useful in the modeling of physical objects that move. It is difficult to provide high quality algorithms for handling all of these varied types of constraints in a single monolithic solver program. Therefore, what is desirable is to allow the modeling application to dynamically use solver programs from a number of sources. This permits the same modeling application to be used across a broader class of modeling problems than the monolithic solver program approach.
The weakness of previous modeling systems in handling large numbers of interdependent model objects grew out of the solution techniques used. Previous approaches apply iterative numeric approximations to the entire model. However it is desirable to allow the user to provide specific solver programs for various problem types, the best techniques for handling interdependent model objects can be used.
Research done at the Massachusetts Institute of Technology in 1987 identified strategies for satisfying constraints among a mix of problem types. See D. Serrano, Constraint Management in Conceptual Design, Ph.D. Thesis, Massachusetts Institute of Technology, October 1987. Serrano discusses, among other topics, the creation of directed graphs based upon a set of constraint definitions. To evaluate directed graphs with cycles, Serrano suggests collapsing the cycles into supemodes. However, Serrano's does not discuss graphs with directed and nondirected constraints. Directional constraints, also called unidirectional constraints, are constraints that cause a deterministic change to a set of output objects, given a predetermined set of "input" model objects. The cause and effect relationship is specific to the constraint's definition and is known without further context. An example is a boolean operation constraint such as a boolean intersection constraint of a box model object and a sphere object produces a new model object. The new model object will be deterministically changed by the input model objects and the boolean operation. Nondirectional constraints, also called bidirectional or multidirectional constraints, are those constraints which specify a condition which must be met, but do not inherently specify the cause/effect relationship without additional context. Typically, this additional context is supplied by other nondirected constraints during a simultaneous solution approach in a particular kind of solver program (described below). An example of a nondirected constraint is a parallel constraint between two line model. Additional context is required for the new model object to be completely determined. Instead, Serrano describes converting the entire graph into a directed graph, then collapsing cycles into supernodes. The graph is then evaluated to determine the missing values of the parameters in the constraints.
Another problem with the previous systems was that the entire model had to be reevaluated after changes. That made it difficult to provide on-the-fly constraint satisfaction. Therefore, it is desirable to have a system that can provide on-the-fly constraint satisfaction as the model is changed. Another problem of the previous systems was that no feedback was given on-the-fly if solver programs would be unable to satisfy constraints as they were input. Therefore, it is desirable to provide feedback to the user on-the-fly to indicate constraints which are unsolvable. Another problem with the previous systems was that the user could not specify criteria such as speed, accuracy, cost of use, etc., to control the selection of solver programs. Therefore, it is desirable to provide a mechanism for the user to control the selection of solver programs.
The previous approaches have never been combined to provide a broad efficient constraint satisfier for multiple problem types. Thus, there is a need for an improved method of constraint satisfaction in modeling systems.